package com.exercises;


class Exercise44 {
    public static void main(String[] args) {
        String s = "1234567";
        String p = "123*";
        System.out.println(new Exercise44().isMatch(s, p));
    }


    public boolean isMatch(String s, String p) {
        int sl = s.length() + 1;
        int pl = p.length() + 1;
        int[][] result = new int[sl][pl];
        for (int i = 0; i < sl; i++) {
            for (int j = 0; j < pl; j++) {

                if (i == 0 && j == 0) {
                    //验证字符串是空串 表达式也是空串
                    result[i][j] = 1;
                    show(result);
                    continue;
                }
                if (j == 0) {
                    //验证字符串不为空,表达式为空 不匹配
                    continue;
                }

                if (i == 0) {
                    if (result[i][j - 1] == 1 && "*".equals(p.charAt(j - 1) + "")) {
                        //验证字符串是空串,表达是不为空串  例子 s:"" p:"***"
                        result[i][j] = 1;
                        show(result);
                    }
                    continue;
                }


                String sChar = s.charAt(i - 1) + "";
                String pChar = p.charAt(j - 1) + "";
                if (sChar.equals(pChar) || "?".equals(pChar)) {
                    //当前位置与验证位置一致或者?
                    result[i][j] = result[i - 1][j - 1];
                    show(result);
                } else if ("*".equals(pChar)) {
                    //*代表任意字符
                    if (result[i - 1][j - 1] == 1) {
                        result[i][j] = 1;
                    }
                    //*代表空字符
                    if (result[i][j - 1] == 1) {
                        result[i][j] = 1;
                    }
                    //*代表多个字符
                    if (result[i - 1][j] == 1) {
                        result[i][j] = 1;
                    }
                    show(result);
                }
            }
        }


        return result[sl - 1][pl - 1] == 1;
    }


    private static void show(int[][] result) {

        for (int i = 0; i < result[1].length; i++) {
            for (int j = 0; j < result.length; j++) {
                System.out.print(result[j][i]);
                System.out.print(" ");
            }
            System.out.println();
        }
        System.out.println("======================");
    }

}

